package test.algorithm.dp;

/**
 * @Projectname: leetCode
 * @Filename: FbSequence
 * @Author: FANSEA
 * @Date:2024/9/10 16:45
 */

/**
 * 斐波那契数列
 */
public class FbSequence {

    public int fib(int n) {
        char c = "abc".charAt(0);
        if (n==0 || n==1) {
            return n;
        }
        return fib(n-1)+fib(n-2);
    }
    public int fibPlus(int n) {
        // 动态规划
        int[] fib = new int[n+1];
        fib[0] = 0;
        if(n>0){
            fib[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        return fib[n];
    }
}
